/**
 * 快速排序
 */
public class QuickSort extends TemplateSort {

    @Override
    void sort(Comparable[] a) {
        sort(a, 0, a.length - 1);
    }

    /**
     * 递归
     * @param a
     * @param lo
     * @param hi
     */
    public void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        // 切分
        int j = partition(a, lo, hi);

        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }

    /**
     * 将数组切分为 a[lo..i-1], a[i], a[i+1..hi]
     * @param a
     * @param lo
     * @param hi
     * @return
     */
    private int partition(Comparable[] a, int lo, int hi) {
        int i = lo, j = hi + 1; // 左右扫描指针
        Comparable v = a[lo]; // 切分元素

        while (true) {
            // 扫描左右，检查扫描是否结束并交换元素
            while (less(a[++i], v)) {
                if (i == hi) {
                    break;
                }
            }
            while (less(v, a[--j])) {
                if (j == lo) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }

            exch(a, i, j);
        }
        // 将 v = a[j] 放入正确的位置
        exch(a, lo, j);
        // a[lo..j-1] <= a[j] <= a[j+1..hi] 达成
        return j;
    }

    public static void main(String[] args) {
        TemplateSort templateSort = new QuickSort();

        Comparable[] data = templateSort.createInt(0, 1000, 300);

        templateSort.run(data);
    }
}
